package LeetCode;

public class LC_214_ShortestPalindrome {

    public static void main(String[] args) {

    }

    static class Solution {
        public String shortestPalindrome(String s) {
            if (s.length() <= 1) return s;
            int center = (s.length() - 1) / 2;
            String res = "";
            for (int i = center; i >= 0; i--) {
                if (s.charAt(i) == s.charAt(i + 1))
                    if ((res = check1(s, i, i + 1)) != null) return res;
                if ((res = check1(s, i, i)) != null) return res;
            }
            return res;
        }

        private String check1(String s, int l, int r) {
            int i = 1;
            for (; l - i >= 0 && r + i < s.length(); i++)
                if (s.charAt(l - i) != s.charAt(r + i)) break;

            if (l - i >= 0) return null;
            StringBuilder sb = new StringBuilder(s.substring(r + i));
            sb.reverse();
            return sb + s;
        }

    }

    public class Solution_2 {
        public String shortestPalindrome(String s) {
            int i = 0, end = s.length() - 1, j = end;
            char[] arr = s.toCharArray();
            while (i < j) {
                if (arr[i] == arr[j]) {
                    ++i;
                    --j;
                } else {
                    i = 0;
                    --end;
                    j = end;
                }
            }
            return new StringBuilder(s.substring(end + 1)).reverse().toString() + s;
        }
    }

    public class Solution_3 {
        public String shortestPalindrome(String s) {
            String r = new StringBuilder(s).reverse().toString();
            String t = s + "#" + r;
            int[] next = new int[t.length()];
            for (int i = 1; i < t.length(); ++i) {
                int j = next[i - 1];
                while (j > 0 && t.charAt(i) != t.charAt(j)) j = next[j - 1];
                j += (t.charAt(i) == t.charAt(j)) ? 1 : 0;
                next[i] = j;
            }
            return r.substring(0, s.length() - next[t.length() - 1]) + s;
        }
    }

}